Search for: All records

In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x < a 0 is ⩽ a 1 . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ 2 0 -enumeration degrees  a 0 and  a 1 such that every enumeration degree x 0 < a 0 is ⩽ a 1 and such that every enumeration degree x 1 < a 1 is ⩽ a 0 . In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that both ( a 0 , a 1 ) and ( a 1 , a 2 ) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ 2 0 -enumeration degrees  a 0 , a 1 and  a 2 such that every enumeration degree x < a 0 is also ⩽ a 1 or ⩽ a 2 ; however neither ( a 0 , a 1 ) nor ( a 0 , a 2 ) is an Ahmad pair. 

Abstract The tower number $${\mathfrak t}$$ and the ultrafilter number $$\mathfrak {u}$$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $$\omega $$ and the almost inclusion relation $$\subseteq ^*$$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $$(G_n)_{n \in {\mathbb N}}$$ of computable sets is a tower if $$G_0 = {\mathbb N}$$ , $$G_{n+1} \subseteq ^* G_n$$ , and $$G_n\smallsetminus G_{n+1}$$ is infinite for each n . A tower is maximal if there is no infinite computable set contained in all $$G_n$$ . A tower $${\left \langle {G_n}\right \rangle }_{n\in \omega }$$ is an ultrafilter base if for each computable R , there is n such that $$G_n \subseteq ^* R$$ or $$G_n \subseteq ^* \overline R$$ ; this property implies maximality of the tower. A sequence $$(G_n)_{n \in {\mathbb N}}$$ of sets can be encoded as the “columns” of a set $$G\subseteq \mathbb N$$ . Our analogs of $${\mathfrak t}$$ and $${\mathfrak u}$$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $$\Delta ^0_2$$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. 

Abstract We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel quotient of the reals reduces to it. 

Abstract Recall that B is PA relative to A if B computes a member of every nonempty $$\Pi ^0_1(A)$$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $$\Pi ^0_1$$ class relative to an enumeration oracle A , which they called a $$\Pi ^0_1{\left \langle {A}\right \rangle }$$ class. We study the induced extension of the relation B is PA relative to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the $${\left \langle {\text {self}\kern1pt}\right \rangle }$$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $$\Pi ^0_1$$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question. 

The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees, we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. We prove that the enumeration degree of A is continuous if and only if A is codable, meaning that A is enumeration above the complement of an infinite tree, every path of which enumerates A. 

Fix an r-coloring of the pairs of natural numbers. An ordered list of distinct integers, is a monochromatic path for color k, if every two adjacent integers in the list have the same color. A path decomposition for the coloring is a collection of r paths P0,P1,...,Pr−1 such that Pj is a path of color j and every integer appears on exactly one path. Improving on an unpublished result of Erdos, Rado published a theorem which implies: Every r- coloring of the pairs of natural numbers has a path decomposition. We analyse the effective content of this theorem.